package me.algo.tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Objects;

/**
 * @author guozheng
 * @date 2024/4/19
 */
public class T8 {
    public static void main(String[] args) {

    }

    /**
     * 513. 找树左下角的值
     * 层序遍历  最后一行的第一个元素
     *
     * @param root
     * @return
     */
    public static int findBottomLeftValue(TreeNode root) {
        Objects.requireNonNull(root);
        int left = root.val;
        LinkedList<TreeNode> que = new LinkedList<>();
        que.addLast(root);
        while (!que.isEmpty()) {
            int size = que.size();
            int z = size;
            while (size > 0) {
                TreeNode node = que.removeFirst();
                if (size == z) {
                    left = node.val;
                }
                size--;
                if (node.left != null) {
                    que.addLast(node.left);
                }
                if (node.right != null) {
                    que.addLast(node.right);
                }
            }
        }
        return left;
    }


    /**
     * 515. 在每个树行中找最大值
     * 层序遍历  找最大
     * @param root
     * @return
     */
    public List<Integer> largestValues(TreeNode root) {
        if (Objects.isNull(root)) {
            return new ArrayList<>();
        }
        LinkedList<TreeNode> que = new LinkedList<>();
        List<Integer> levelMaxList = new ArrayList<>();

        que.addLast(root);
        while (!que.isEmpty()) {
            int size = que.size();
            int levelMax = Integer.MIN_VALUE;
            while (size > 0) {
                size--;
                TreeNode node = que.removeFirst();
                if (levelMax < node.val) {
                    levelMax = node.val;
                }
                if (node.left != null) {
                    que.addLast(node.left);
                }
                if (node.right != null) {
                    que.addLast(node.right);
                }
            }
            levelMaxList.add(levelMax);
        }
        return levelMaxList;
    }

    /**
     * 199. 二叉树的右视图
     * @param root
     * @return
     */
    public List<Integer> rightSideView(TreeNode root) {
        if (Objects.isNull(root)) {
            return new ArrayList<>();
        }
        List<Integer> rtn = new ArrayList<>();
        LinkedList<TreeNode> que = new LinkedList<>();
        que.addLast(root);
        while (!que.isEmpty()) {
            int size = que.size();
            int f = size;
            while (size > 0) {
                TreeNode node = que.removeFirst();
                if (f == size) {
                    rtn.add(node.val);
                }
                if (node.right != null) {
                    que.addLast(node.right);
                }
                if (node.left != null) {
                    que.addLast(node.left);
                }
                size--;
            }
        }
        return rtn;
    }


    /**
     * 662. 二叉树最大宽度
     * @param root
     * @return
     */
    public int widthOfBinaryTree(TreeNode root) {
        if (Objects.isNull(root)) {
            return 0;
        }
        LinkedList<Pair> que = new LinkedList<>();
        que.addLast(new Pair(root, 1));
        int maxWidth = 1;
        while (!que.isEmpty()) {
            int size = que.size();
            int z = size;
            int lineLeft = 0;
            int lineRight = 0;
            while (size > 0) {
                Pair pair = que.removeFirst();
                TreeNode node = pair.node;
                if (size == z) {
                    lineRight = pair.num;
                }
                if (size == 1) {
                    lineLeft = pair.num;
                }
                if (node.right != null) {
                    que.addLast(new Pair(node.right, pair.num * 2 + 1));
                }
                if (node.left != null) {
                    que.addLast(new Pair(node.left, pair.num * 2));
                }
                size--;
            }
            int lineWidth = lineRight - lineLeft + 1;
            if (lineWidth > maxWidth) {
                maxWidth = lineWidth;
            }
        }
        return maxWidth;
    }

    /**
     * 662配套类
     * @param node
     * @param num
     */
    record Pair(TreeNode node, int num) {
    }


    /**
     * 1161. 最大层内元素和
     * @param root
     * @return
     */
    public int maxLevelSum(TreeNode root) {
        Objects.requireNonNull(root);
        int maxVal = Integer.MIN_VALUE;
        int maxLevel = -1;
        int level = 1;
        LinkedList<TreeNode> que = new LinkedList<>();
        que.addLast(root);
        while (!que.isEmpty()) {
            int size = que.size();
            int levelSum = 0;
            while (size > 0) {
                size--;
                TreeNode node = que.removeFirst();
                levelSum = levelSum + node.val;
                if (node.left != null) {
                    que.addLast(node.left);
                }
                if (node.right != null) {
                    que.addLast(node.right);
                }
            }
            if (levelSum > maxVal) {
                maxVal = levelSum;
                maxLevel = level;
            }
            level++;
        }
        return maxLevel;
    }
}
